package com.bichengcao.googlecodejam.practiceproblems;

import java.io.BufferedReader;
import java.io.FileReader;
import java.io.FileWriter;
import java.io.IOException;
import java.io.PrintWriter;

public class AlienNumbers {

	static int N;

	public static void main(String[] args) throws IOException {
		Input[] inputs = parseInput("src/com/bichengcao/googlecodejam/practiceproblems/A-large-practice.in");
		Output[] outputs = process(inputs);
		writeOutput("src/com/bichengcao/googlecodejam/practiceproblems/AlienNumbers.out", outputs);
	}

	static class Input {

		String alienNumber;
		String sourceLanguage;
		String targetLanguage;
	}

	static class Output {

		String alienNumber = "";
	}

	private static Input[] parseInput(String filename) throws IOException {
		BufferedReader in = new BufferedReader(new FileReader(filename));
		N = Integer.parseInt(in.readLine());
		Input[] array = new Input[N];

		for (int i = 0; i < N; i++) {
			Input input = array[i] = new Input();
			String line = in.readLine();
			String[] splits = line.split(" ");
			input.alienNumber = splits[0];
			input.sourceLanguage = splits[1];
			input.targetLanguage = splits[2];
		}

		in.close();
		return array;
	}

	private static Output[] process(Input[] inputs) {
		Output[] outputs = new Output[N];
		for (int i = 0; i < N; i++) {
			outputs[i] = process(inputs[i]);
		}
		return outputs;
	}

	private static Output process(Input input) {
		Output output = new Output();

		// Convert the alien number in source language to decimal
		int value = 0;
		for (int i = 0; i < input.alienNumber.length(); i++) {
			char c = input.alienNumber.charAt(i);
			value = value * input.sourceLanguage.length() + input.sourceLanguage.indexOf(c);
		}
		// Convert the number from decimal to target language
		while (value != 0) {
			output.alienNumber = input.targetLanguage.charAt(value % input.targetLanguage.length())
					+ output.alienNumber;
			value /= input.targetLanguage.length();
		}

		return output;
	}

	private static void writeOutput(String filename, Output[] outputs) throws IOException {
		PrintWriter out = new PrintWriter(new FileWriter(filename));
		for (int i = 0; i < N; i++) {
			out.println("Case #" + (i + 1) + ": " + outputs[i].alienNumber);
		}
		out.close();
	}

}
